#include<iostream>//zju 2334 
#include<cstdio>
using namespace std;
const int N=100010; 
int fa[N];
/*************左偏堆模板(大根堆)*********************/
struct node{//0表示空节点//如果要大根堆变成小根堆，健值为负数就行了
	int k,dis;//k是健值，dis是距离
	int l,r,f,sz;//l是左，r是右，f是父亲,sz左偏堆的儿子和自己个数
	node(){}
	node(int a):k(a),dis(0),l(0),r(0),f(0),sz(1){}
}tr[2*N];
inline int troot(int a){//找堆顶元素的下标
	if(!a)return 0;
	while(tr[a].f)a=tr[a].f;
	return a;
}
inline int tmerge(int x,int y){//合并x与y堆
	int sz=tr[x].sz+tr[y].sz;
	if(!(x*y))return x+y; 
	if( tr[x].k<tr[y].k)	swap(x,y);
	int r=tmerge(tr[x].r,y),	l=tr[x].l;
	tr[x].r=r;tr[r].f=x;
	if(tr[r].dis>tr[l].dis)	swap(tr[x].l,tr[x].r);
	if(r) tr[x].dis=tr[r].dis+1;
	else tr[x].dis=0;
	tr[x].sz=sz;
	return x;
}
inline int tins(int i,int k,int& root){//在root下加一个元素i
	tr[i]=node(k);
	return root=tmerge(root,i);
}
inline node tpop(int& root){//取堆顶的，并且弹出堆顶元素
	node out=tr[root];
	int l=tr[root].l,r=tr[root].r;
	tr[root]=node(tr[root].k);
	tr[l].f=tr[r].f=0;
	root=tmerge(l,r);
	return out;
}
inline int tdel(int u){//删除u这个节点,返回现在的根
	if(!u)return u;
	int x,y,l,r;
	int &yl=tr[y].l,&yr=tr[y].r;//这里两个都要写引用吗？
	l=tr[u].l;r=tr[u].r;y=tr[u].f;
	tr[u]=node(tr[u].k);
	tr[x=tmerge(l,r)].f=y;
	if(y &&  yl==u) yl=x;
	if(y &&  yr==u) yr=x;
	for(;y;x=y,y=tr[y].f){
		if(tr[yr].dis>tr[yl].dis)swap(yl,yr);
		if(tr[yr].dis+1==tr[y].dis)break;
		tr[y].dis=tr[yr].dis+1;
	}
	if(x)return troot(x);
	else return troot(y);
}
inline int tadd(int i,int v){//tr[i].key+=v //返回根节点
	if(!i)return i;
	if(!(tr[i].l+tr[i].r+tr[i].f)){
		tr[i].k+=v;return i;
	}
	int kk=tr[i].k+v;
	int rt=tdel(i);
	return tins(i,kk,rt);
}
/*************左偏堆模板*********************/
int find(int x)
{
	int faa,t=x;
	while(fa[x]!=x)
	{
		x=fa[x];
	}
	faa=x;
	x=t;
	while(fa[x]!=x)
	{
		int tp=fa[x];
		fa[x]=faa;
		x=tp;
	}
	return faa;
}
int n,m;
int main()
{
	//freopen("in","r",stdin);
	int i,j,k;
	while(scanf("%d", &n)!=EOF)
	{
	int x,y;
		for(i=1; i<=n ; i++)
		{
			scanf("%d",&x);
/**先把元素排序，然后建堆，注意1->n本来就是堆的顺序，所以直接合并就是***由于此题是有序的，所以可以直接就建成堆*/			
			tr[i]=node(x);
			fa[i]=i;
		}
		scanf("%d",&m);
		while(m--)
		{
			scanf("%d%d",&x,&y);
			int u=find(x);
			int v=find(y);			
			if(v==u)
			{
				printf("-1\n");
			}
			else
			{
				int aa=troot(u);
				int bb=troot(v);
				fa[u]=v;
				aa=tadd( aa,tr[aa].k/2-tr[aa].k);
				bb=tadd( bb,tr[bb].k/2-tr[bb].k);
				aa=tmerge(aa,bb);
				printf("%d\n",tr[aa].k);
			}
		}
	}	
}
